package solutions.leetcode.hard;

import solutions.lib.BaseSolution;

import java.util.PriorityQueue;

/**
 * @author lizhidong
 * <a href="https://leetcode-cn.com/problems/k-th-smallest-prime-fraction/">786. 第 K 个最小的素数分数</a>
 */
public class Solution786 extends BaseSolution {

    public int[] kthSmallestPrimeFraction(int[] arr, int k) {
        class Model {

            final int v1;
            final int v2;

            public Model(int v1, int v2) {
                this.v1 = v1;
                this.v2 = v2;
            }
        }
        PriorityQueue<Model> priorityQueue = new PriorityQueue<>((m1, m2) -> m1.v2 * m2.v1 - m1.v1 * m2.v2);
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < i; j++) {
                priorityQueue.offer(new Model(arr[j], arr[i]));
                if (priorityQueue.size() > k) {
                    priorityQueue.poll();
                }
            }
        }
        Model max = priorityQueue.peek();
        return new int[] {max.v1, max.v2};
    }

    public static void main(String[] args) {
        Solution786 solution = new Solution786();
        printVals(solution.kthSmallestPrimeFraction(new int[]{
                1, 2, 3, 5
        }, 3));
    }
}